1. Technical Field
The present invention is related to computer graphics, and more particularly to a system and method for synthesizing a texture from a sample texture.
2. Background
Various techniques have been utilized to render graphical images via computer systems. One representation of visual images is referred to as a texture. A texture refers to a graphics data structure which models the surface appearance of an object. A texture may represent the visual experience of many materials and substances (e.g., terrain, plants, minerals, fur, and skin). Textures may be created digitally by sampling a physical surface utilizing photographic techniques. Alternatively, textures may be created manually utilizing a suitable graphics design application.
Texture synthesis refers to creating a new texture of a selected size from a sample texture of a fixed size. For example, FIG. 1A depicts exemplary texture 101. Texture 101 includes a distribution of diamonds and stars. Although the diamonds and stars appear to be distributed in a semblance of order, a degree of randomization is apparent. The diamonds and stars seem to be arranged according to a stochastic process. FIG. 1B depicts exemplary synthesized texture 102. Synthesized texture 102 is not merely an enlarged or upscaled version of texture 101. Synthesized texture 102 possesses approximately the same degree of detail per unit of area as texture 101. The distribution of diamonds and stars in synthesized texture 102 does not exactly correspond to the distribution in texture 101. However, it appears that the same stochastic process has generated the distribution of synthesized texture 102.
Synthesizing a new texture that appears to an observer to have been generated from the same stochastic process can be quite challenging. In particular, interpolation techniques (such as Fourier coefficient algorithms) are not helpful because the level of visual detail as a function of area is not maintained in the larger synthesized texture. Moreover, boundary conditions present a number of difficulties. In particular, seams and repetitions may be visually evident, thereby reducing the realism of the synthesized texture.
A texture synthesis algorithm has been developed by Li-Yi Wei and Marc Levoy which addresses the preceding texture synthesis issues. The algorithm is described in Fast Texture Synthesis Using Tree-Structured Vector Quantization, Li-Yi Wei and Marc Levoy, SIGGRAPH 2000 Conference Proceedings, pg. 479–488, the disclosure of which is hereby incorporated herein by reference. The algorithm begins by utilizing a texture of a given size to generate a texture of some arbitrary larger size. Wei and Levoy describe (a) modeling or estimating the stochastic process associated with the original texture and (b) sampling from the original texture to synthesize or produce the new texture having the larger size. At a high level, the algorithm synthesizes the new texture by modeling the original texture using Markov Random Field concepts. The algorithm assembles the new texture in a pixel by pixel manner. Each pixel of the new matrix is determined by comparing its “neighborhood” to all neighborhoods in the original matrix.
Specifically, the synthesis algorithm taught by Wei and Levoy begins by receiving a data structure defining a texture. The data structure is a matrix of red-green-blue (RGB) values defining the texture, where RGB is a well-known encoding method for representing the red, green, and blue chromatic channels of a pixel. A second matrix is created that is equal in size to the desired size of the texture to be synthesized. The second matrix is initialized with white random noise.
The algorithm proceeds by examining each pixel of the second matrix in raster scan order (e.g., from left to right and top to bottom). The algorithm transforms each pixel by first determining the neighborhood of each pixel. The neighborhood refers to a group of pixels that are relatively adjacent to the respective pixel of the second matrix. Also, the neighborhood is preferably chosen to be causal. Specifically, it is selected so that it only contains pixels that have already been synthesized and not pixels containing noise values. For example, FIG. 1C depicts exemplary matrix 103. Matrix 103 comprises pixel 104 and exemplary neighborhood 105. Neighborhood 105 only contains pixels that are previous to pixel 104 in the raster scan order. It shall be appreciated that this is not always possible. Accordingly, the first few pixels are allowed to contain neighborhoods with noise values. However, after a number of pixels have been synthesized, it is preferred to only utilize causal neighborhoods. Also, when a pixel is selected that is close to an edge of the matrix, the neighborhood may be selected in a toroidal manner, i.e., the neighborhood wraps around to the other side of the matrix.
The value of each respective pixel is assigned by comparing it to each pixel in the original matrix. Specifically, each pixel of the second matrix is assigned the color of the pixel in the original matrix that possesses a neighborhood that most closely matches the respective neighborhood of the pixel to be synthesized. The determination of most-closely matching neighborhoods is performed by utilizing a simple norm (sum of square differences) calculation. For example, R1, G1, B1 may represent the red, green, and blue components or channels of a pixel in a neighborhood of the original or sample texture. R2, G2, B2 may represent the red, green, and blue components or channels of a corresponding pixel in a neighborhood of the texture to be synthesized. The square of the difference equals (R1−R2)2+(G1−G2)2+(B1−B2)2. The sum of the differences then equals the summation of the previous calculation for each pixel pair between the two neighborhoods. The lowest norm corresponds to the most closely matching neighborhood.
Wei and Levoy also describe optimizations to the algorithm. First, multi-resolution synthesis is described to adapt to larger sized neighborhoods. The multi-resolution synthesis operates by building Gaussian pyramids from the original matrix and the noise matrix. A Gaussian pyramid is a hierarchy of low-pass filtered versions of the original image, such that successive levels correspond to lower frequencies. The Gaussian pyramid is produced by low-pass filtering via convolution with a Gaussian filter kernel. The algorithm proceeds by transforming the noise Gaussian pyramid from lower to higher resolutions. The only modification for the multi-resolution case is that each neighborhood contains pixels in the current resolution and all lower resolutions.
Wei and Levoy further describe acceleration of the algorithm utilizing tree-structured vector quantization (TSVQ). As described in Vector Quantization and Signal Compression, A. Gersho and R. M. Gray (1992), the disclosure of which is hereby incorporated herein by reference, TSVQ is a well-known technique for data compression. The tree generated by TSVQ may be used as a data structure for efficient nearest-point queries. To find the nearest point of a given query vector, the tree is traversed from the root in a best-first ordering by comparing the query vector with the two children codewords and then following the one that has a closer codeword. This process is repeated for each visited node until a leaf node is reached. The best codeword is then returned as the codeword of that leaf node. Unlike full searching, the result codeword may not be the best or closest one, since only part of the tree is traversed. However, the result codeword usually approximates the exact solution, and the computation is more efficient than full searching.
To use TSVQ in the synthesis algorithm, the set of neighborhood pixels are collected for each input pixel and treated as a vector of a size equal to the number of pixels in the neighborhood. The vectors for each neighborhood are used as the training data to generate the corresponding tree structure codewords. During the synthesis process, the (approximate) closest point neighborhood is found by performing a best-first traversal of the binary-tree structure.